package com.zhugang.week03;

/**
 * @program algorithms
 * @description: arrayQueue
 * @author: chanzhugang
 * @create: 2022/06/02 21:24
 */
public class ArrayQueue {

    private final String[] items;
    private final int n;
    private int head;
    private int tail;

    public ArrayQueue(int capacity) {
        this.n = capacity;
        this.items = new String[capacity];
    }


    /**
     * 入队：集中触发数据搬移,时间复杂度有点高（特殊情况O(n)）,因此还有更好的实现方式，循环队列
     *
     * @param item
     * @return
     */
    public boolean enqueue(String item) {
        if (tail == n) {
            // tail == n && head == 0时队列满了
            if (head == 0) return false;
            for (int i = head; i < tail; i++) {
                // 数据搬移
                items[i - head] = items[i];
            }
            head = 0;
            tail -= head;
        }
        items[tail] = item;
        tail++;
        return true;
    }

    /**
     * 出队
     *
     * @return
     */
    public String dequeue() {
        // head == tail,表示队列为空
        if (head == tail) return null;
        String item = items[head];
        head++;
        return item;
    }

}